package com.tgy.programmer_code_interview_guide._02_linkedList;

import com.tgy.leetcode.ListNode;
import com.tgy.leetcode.TreeNode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/27/21 1:43 PM
 */
public class _12_将搜索二叉树转换成链表 {

    public static ListNode searchBinaryTreeToLinkedList(TreeNode treeNode) {


        ListNode dummyNode = new ListNode(0);
        ListNode tailNode = dummyNode;

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = treeNode;
        while (true) {

            while (node != null) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                break;
            }

            node = stack.pop();

            ListNode tmpNode = new ListNode(node.val);

            if (tailNode != dummyNode) {
                tmpNode.pre = tailNode;
            }

            tailNode.next = tmpNode;
            tailNode = tmpNode;

            node = node.right;
        }

        tailNode.next = null;

        return dummyNode.next;
    }

    public static void main(String[] args) {

        TreeNode root = new  TreeNode(3);

        root.left = new TreeNode(1);
        root.right = new TreeNode(5);

        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(4);

        ListNode listRoot = searchBinaryTreeToLinkedList(root);

        ListNode.printListNode(listRoot);

    }
}
